#include<bits/stdc++.h>
using namespace std;
#define INF 1e7
int t[2001][2001];
int l[2001];
int n;
int main()
{
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    int y;
    cin>>y;
    while(y--)
    {
        cin>>n;
        long long ans=0;
        for(int i=0;i<=n;i++)
            for(int j=0;j<=n;j++) t[i][j]=-INF;
        for(int i=1;i<=n;i++) cin>>l[i];
        t[0][0]=0;
        for(int i=1;i<=n;i++) t[0][i]=t[i][0]=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                /*if(l[i]==l[j])
                {
                    for(int ti=1;ti<=j;ti++)
                    {
                        t[i][ti]=max(max(t[ti][i]+l[j],t[ti][j]),t[ti-1][j]);
                        t[ti][j]=max(max(t[i][ti]+l[j],t[j][ti]),t[j][ti-1]);
                    }
                }
                else
                {
                    for(int ti=1;ti<=j;ti++)
                    {
                        t[ti][j]=max(t[ti][i],t[ti-1][j]);
                        t[j][ti]=max(t[i][ti],t[j][ti-1]);
                    }
                }*/
                if(i==j) continue;
                if((i+1==j)||(j+1==i))
                {
                    for(int ti=0;ti<max(j,i);ti++)
                    {
                        if(ti<i){
                        if((l[i]==l[ti])) t[i][j]=max(t[i][j],t[ti][j]+l[i]);
                        else t[i][j]=max(t[i][j],t[ti][j]);}
                        if(ti<j){
                        if((l[j]==l[ti])) t[i][j]=max(t[i][j],t[i][ti]+l[j]);
                        else t[i][j]=max(t[i][j],t[i][ti]);}
                    }
                }
                else
                {
                    if(l[i]==l[i-1]) t[i][j]=max(t[i][j],t[i-1][j]+l[i]);
                    else t[i][j]=max(t[i][j],t[i-1][j]);
                    if((l[j]==l[j-1])) t[i][j]=max(t[i][j],t[i][j-1]+l[j]);
                    else t[i][j]=max(t[i][j],t[i][j-1]);
                }
            }
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++) ans=max((long long)t[i][j],ans);
        cout<<ans<<endl;
    }
    return 0;
}
